//现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 
//prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。 
//
// 
// 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。 
// 
//
// 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。 
//
// 
//
// 示例 1： 
//
// 
//输入：numCourses = 2, prerequisites = [[1,0]]
//输出：[0,1]
//解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
// 
//
// 示例 2： 
//
// 
//输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
//输出：[0,2,1,3]
//解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
//因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。 
//
// 示例 3： 
//
// 
//输入：numCourses = 1, prerequisites = []
//输出：[0]
// 
//
// 
//提示：
//
// 
// 1 <= numCourses <= 2000 
// 0 <= prerequisites.length <= numCourses * (numCourses - 1) 
// prerequisites[i].length == 2 
// 0 <= ai, bi < numCourses 
// ai != bi 
// 所有[ai, bi] 互不相同 
// 
// Related Topics 深度优先搜索 广度优先搜索 图 拓扑排序 👍 654 👎 0

package leetcode.editor.cn;

import java.util.*;

class CourseScheduleIi {
    public static void main(String[] args) {
        Solution solution = new CourseScheduleIi().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // DFS
        /*boolean[] onPath;
        boolean[] visited;
        boolean isCycle;
        List<Integer> res = new ArrayList<>();  // 记录遍历的结果

        public int[] findOrder(int numCourses, int[][] prerequisites) {
            List<Integer>[] graph = buildGraph(numCourses, prerequisites);
            onPath = new boolean[numCourses];
            visited = new boolean[numCourses];

            for (int i = 0; i < numCourses; i++) {
                traversal(graph, i);
            }

            // 如果有环不能进行拓扑排序
            if (isCycle) {
                return new int[]{};
            }

            // 反转后序遍历，就可以得到拓扑排序的一个结果
            Collections.reverse(res);
            int[] ints = new int[res.size()];
            for (int i = 0; i < ints.length; i++) {
                ints[i] = res.get(i);
            }
            return ints;
        }

        // 后序遍历，获取路径
        public void traversal(List<Integer>[] graph, int s) {
            // 如果出现了环
            if (onPath[s]) {
                isCycle = true;
            }

            if (visited[s] || isCycle) {
                return;
            }

            onPath[s] = true;
            visited[s] = true;
            for (Integer t : graph[s]) {
                traversal(graph, t);
            }
            // 加入路径
            res.add(s);
            onPath[s] = false;
        }*/

        public List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
            LinkedList<Integer>[] graph = new LinkedList[numCourses];
            for (int i = 0; i < numCourses; i++) {
                graph[i] = new LinkedList<>();
            }

            for (int[] edge : prerequisites) {
                int from = edge[1], to = edge[0];
                graph[from].add(to);
            }
            return graph;
        }

        // BFS
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            // 构建临接表
            List<Integer>[] graph = buildGraph(numCourses, prerequisites);

            // 计算出每个节点的入度数
            int[] indegree = new int[numCourses];
            for (int[] edge : prerequisites) {
                int from = edge[1], to = edge[0];
                // 入度加一
                indegree[to]++;
            }

            // 将入度为0的节点入栈
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < numCourses; i++) {
                if (indegree[i] == 0) {
                    queue.offer(i);
                }
            }

            // 记录拓扑排序结果
            int[] res = new int[numCourses];
            // 记录遍历节点的顺序（索引）
            int count = 0;
            // 开始执行 BFS 算法
            while (!queue.isEmpty()) {
                Integer cur = queue.poll();
                res[count] = cur;
                count++;
                // 此时这个节点取走了，那么他所指向的节点入度减一
                for (Integer next : graph[cur]) {
                    indegree[next]--;
                    // 如果有度为0的，直接入队
                    if (indegree[next] == 0) {
                        queue.offer(next);
                    }
                }
            }

            // 存在环
            if (count != numCourses) {
                return new int[]{};
            }

            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
